La teoría de límites de gráficas y el lema de regularidad de Szemerédi (vía martingalas).

Resumen:

El lema de regularidad de Szemerédi surge como una herramienta a la solución de una conjetura de Erdös y Turán dentro de la teoría de números. Este resultado asegura que cualquier gráfica con un número de vértices muy grande tiene una partición del conjunto de vértices de tal manera que las gráficas bipartitas inducidas por dicha partición se comportan de manera aleatoria. Expondré un esbozo de la demostración vía martingalas [1] de este lema en base a una desigualdad reciente [2] que concierne a una sucesión de diferencias de martingala. Se abordará también el lema de Szemerédi desde el área de Análisis como un resultado de aproximación mediante funciones simples y como una herramienta para un resultado de compacidad dentro de la teoría de límites de gráficas [3]. Si el tiempo lo permite, les contaré de un resultado dentro de la teoría de límites de gráficas, análogo a la versión continua del criterio de Erdös-Gallai (en la teoría de gráficas) para una sucesión de grados dada [4].

Bibliografía:

[1] Dodos, P., Kanellopoulos, V., & Karageorgos, T. (2014). Szemerédi's regularity lemma via martingales. https://arxiv.org/abs/1410.5966

[2] Ricard, É., & Xu, Q. (2016). A noncommutative martingale convexity inequality. The Annals of Probability, 44(2), 867-882. https://arxiv.org/abs/1405.0431

[3] Lovász, L. (2012). Large networks and graph limits (Vol. 60). American Mathematical Soc. http://www.ams.org.pbidi.unam.mx:8080/books/coll/060/

[4] Chatterjee, S., Diaconis, P., & Sly, A. (2011). Random graphs with a given degree sequence. The Annals of Applied Probability, 21(4), 1400-1435. https://arxiv.org/abs/1005.1136

Compartir este seminario